package com.zhu.exercise.combination;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;


public class combinationSum2 {

    private List<List<Integer>> result;
    private List<Integer> subans;
    private Map<Integer,Integer> freq = new HashMap<Integer, Integer>(10);
    private int[] tmpNums;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        //准备工作
        List<Integer> cand = new ArrayList<Integer>();
        tmpNums=new int[cand.size()];
        for(int e:candidates){
            cand.add(e);
        }
        Collections.sort(cand);
        tmpNums =cand.stream().mapToInt(Integer::valueOf).toArray();
        cand.stream().forEach(e->{
            if(freq.containsKey(e)){
                freq.put(e,freq.get(e)+1);
            }else{
                freq.put(e,1);
            }
        });

        //开始遍历


        return result;
    }

    /**
     * 递归遍历数组，当rest为0时
     *
     * @param pos 位置
     * @param rest 剩余数量
     */
    public void dfs(int pos,int rest){
        //剩余量为0时添加答案
        if(rest==0){
            result.add(subans);
            return;
        }

        //位置超了退出
        if(pos==tmpNums.length-1||tmpNums[pos]>rest){
            return;
        }

        //不要这个post的数
        dfs(pos+1,rest);

        int most= Math.min(rest/tmpNums[pos],freq.get(tmpNums[pos]));
        for(int i=1;i<most;i++){
            subans.add(tmpNums[pos]);
            dfs(pos+1,rest-tmpNums[pos]);
        }

        //回溯答案
        for(int i=1;i<most;i++){
            subans.remove(subans.size()-1);
        }


    }

    @Test
    public void test(){
        int[] nums = {3,3,8,9,1};
        combinationSum2(nums , 12);
    }
}
